#define _CRT_SECURE_NO_WARNINGS 1

#include "BubbleSort_QuickSort.h"

void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; ++i)
	{
		int tmp = a[i];
		int j = i;
		while (j > 0)
		{
			if (tmp < a[j - 1])
			{
				a[j] = a[j - 1];
				--j;
			}
			else
			{
				break;
			}
		}
		a[j] = tmp;
	}
}

void BubbleSort(int* a, int n)// 冒泡排序
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n - i-1; ++j)
		{
			if (a[j] > a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j+1];
				a[j + 1] = tmp;
			}
		}
	}
}

// 快速排序递归实现
// 快速排序hoare版本
void PartSort1(int* a, int left, int right)
{
	int key = left;
	int begin = left;
	int end = right;
	while (left < right)
	{
		while (right > left && a[right] >= a[key])
		{
			--right;
		}
		while (left < right && a[left] <= a[key])
		{
			++left;
		}
		int tmp = a[right];
		a[right] = a[left];
		a[left] = tmp;
	}
	if (left == right)
	{
		int tmp = a[right];
		a[right] = a[key];
		a[key] = tmp;
		key = right;
		//以key为分界，两个区间[begin,key-1],[key + 1,end]
		int begin1 = begin, end1 = key - 1;
		int begin2 = key + 1, end2 = end;
		PartSort1(a, begin1, end1);
		PartSort1(a, begin2, end2);
	}
}

// 快速排序挖坑法
void PartSort2(int* a, int left, int right)
{
	if (right<0||left>right)
	{
		return;
	}
	int key = a[left];
	int hole = left;
	int begin = left;
	int end = right;
	while (left < right)
	{
		while (left < right && a[right] >=key)
		{
			--right;
		}
		int tmp = a[right];
		a[right] = a[hole];
		a[hole] = tmp;
		hole = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}
		tmp = a[left];
		a[left] = a[hole];
		a[hole] = tmp;
		hole = left;
	}
	a[hole] = key;
	//以key为分界，两个区间[begin,hole-1],[hole + 1,end]
	int begin1 = begin, end1 = hole-1;
	int begin2 = hole + 1, end2 = end;
	PartSort2(a, begin1, end1);
	PartSort2(a, begin2, end2);
}

void PartSort3(int* a, int left, int right)// 快速排序前后指针法
{
	int prev = left;
	int cur = left + 1;
	if (cur > right||left>=right)
	{
		return;
	}
	int key  = left;
	while (cur <= right)
	{
		if (a[cur] <= a[key])
		{
			++prev;
			int tmp = a[cur];
			a[cur] = a[prev];
			a[prev] = tmp;
			++cur;
		}
		else
		{
			++cur;
		}
	}
	int tmp = a[key];
	a[key] = a[prev];
	a[prev] = tmp;
	key = prev;
	//以key为分界，两个区间[left,key-1],[key + 1,right]
	int begin1 = left, end1 = key - 1;
	int begin2 = key + 1, end2 = right;
	PartSort3(a, begin1, end1);
	PartSort3(a, begin2, end2);
}

void QuickSort(int* a, int left, int right)//最终优化版快排(前后指针+三数取中+小区间优化)
{
	
	if (left >= right)
	{
		return;
	}
	if (right - left <= 5)
	{
		InsertSort(a + left, right - left + 1);//小区间优化
	}
	else
	{
		//三数取中选key
		int mid = (left + right) / 2;
		int key = left;
		if (a[left] >= a[right])
		{
			if (a[right] >= a[mid])
			{
				key = right;
			}
			else
			{
				if (a[left] >= a[mid])
				{
					key = mid;
				}
				else
				{
					key = left;
				}
			}
		}
		else
		{
			if (a[left] >= a[mid])
			{
				key = left;
			}
			else
			{
				if (a[mid] >= a[right])
				{
					key = right;
				}
				else
				{
					key = mid;
				}
			}
		}
		int tmp = a[key];
		a[key] = a[left];
		a[left] = tmp;
		key = left;
		int prev = left;
		int cur = left + 1;
		if (cur > right || left >= right)
		{
			return;
		}
		while (cur <= right)
		{
			if (a[cur] < a[key] && ++prev != cur)
			{
				int tmp = a[cur];
				a[cur] = a[prev];
				a[prev] = tmp;
			}
			++cur;
		}
		tmp = a[key];
		a[key] = a[prev];
		a[prev] = tmp;
		key = prev;
		//以key为分界，两个区间[left,key-1],[key + 1,right]
		int begin1 = left, end1 = key - 1;
		int begin2 = key + 1, end2 = right;
		QuickSort(a, begin1, end1);
		QuickSort(a, begin2, end2);
	}
}

void QuickSortNonR(int* a, int left, int right)// 快速排序 非递归实现
{
	Stack st;
	StackInit(&st);
	StackPush(&st, left);
	StackPush(&st, right);
	while (!StackEmpty(&st))
	{
		int end = StackTop(&st);
		StackPop(&st);
		int begin = StackTop(&st);
		StackPop(&st);
		int key = begin;
		int prev = begin;
		int cur = begin + 1;
		while (cur <= end)
		{
			if (a[cur] < a[key]&&++prev !=cur)//前后指针法
			{
				int tmp = a[prev];
				a[prev] = a[cur];
				a[cur] = tmp;
			}
			++cur;
		}
		int tmp = a[prev];
		a[prev] = a[key];
		a[key] = tmp;
		//左区间[begin,prev-1],右区间[prev+1,end]
		int begin1 = begin,end1 = prev-1;
		int begin2 = prev + 1, end2 = end;
		if (begin1 < end1)
		{
			StackPush(&st, begin1);
			StackPush(&st, end1);
		}
		if (begin2 < end2)
		{
			StackPush(&st, begin2);
			StackPush(&st, end2);
		}
	}
    StackDestroy(&st);
}